class QuickSort {
  static sort(arr) {
    QuickSort.quickSort(arr, 0, arr.length - 1);
  }

  static quickSort(arr, l, r) {
    if (l >= r) return; // 数组为空或者是一个元素，那么不需要进行分区操作
    const p = QuickSort.partition(arr, l, r);
    QuickSort.quickSort(arr, l, p - 1);
    QuickSort.quickSort(arr, p + 1, r);
  }

  static partition(arr, l, r) {
    // 取随机值
    const tempPartition = l + Math.floor(Math.random() * (r - l + 1));
    QuickSort.swap(arr, l, tempPartition);
    let j = l;
    // [l+1, j] < v [j+1, i - 1] > v;
    for (let i = l + 1; i <= r; i++) {
      // 从l+1开始遍历
      if (arr[i] < arr[l]) {
        j++;
        QuickSort.swap(arr, j, i);
      }
    }
    QuickSort.swap(arr, l, j);
    return j;
  }

  static swap(arr, i, j) {
    const temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
  }
}

function generateArr(num, end) {
  const arr = [];
  for (let i = 0; i < num; i++) {
    // eslint-disable-next-line no-unused-expressions
    arr[i] = Math.floor(Math.random() * end);
  }
  return arr;
}
const arr = generateArr(20, 100);
console.log(arr);
QuickSort.sort(arr);
console.log(arr);

var twoSum = function (nums, target) {
  const map = {};
  for (let i = 0; i < nums.length; i++) {
    const num = target - nums[i];
    if (map[num] !== undefined) {
      return [i, map[num]];
    }
    map[nums[i]] = i;
  }
};

var reverseList = function(head) {
  let prev = null;
  let cur = head;
  while(cur) {
    const next = cur.next;
    cur.next = prev;//反正链表
    prev = cur;
    cur = next;
  }
  return prev;
};
